package linkcut;

/**
 * Tools for splaying a binary search tree. 
 * @author Arina Buzdalova
 */
public class SplayTools {
	
	/**
	 * Moves the given vertex to the root using zig and zag operations.
	 * @param x the vertex to be moved to the root
	 */
	public final static <V> void splay(AuxVertex<V> x) {
		while (!x.isRoot()) {
			AuxVertex<V> p = x.getParent();
			if (p.isRoot()) {
				Zig(x);
			} else {
				if (x.getType() == p.getType()) {
					ZigZig(x);
				} else {
					ZigZag(x);
				}
			} 
		}
	}
	
	private final static <V> void Zig(AuxVertex<V> x) {
		AuxVertex<V> p = x.getParent();
		AuxVertex<V> g = p.getParent();
		TypeAsChild pType = p.getType();
		
		TypeAsChild xType = x.getType();
		if (g != null) {
			p.detachFromParent();
		}
		if (x.getType() != xType) {
			throw new AssertionError();
		}
		switch (x.getType()) {
		case left: {
			x.detachFromParent();
			AuxVertex<V> mid = x.getRight();
			if (mid != null) {
				mid.detachFromParent();
				p.attachLeft(mid);
			}
			x.attachRight(p);
		} break;
		case right: {
			x.detachFromParent();
			AuxVertex<V> mid = x.getLeft();
			if (mid != null) {
				mid.detachFromParent();
				p.attachRight(mid);
			}
			x.attachLeft(p);
		} break;
		default: throw new IllegalStateException("Strange type: " + x.getType());
		}
		if (g != null) {
			switch (pType) {
			case left: g.attachLeft(x); break;
			case right: g.attachRight(x); break;
			default: throw new IllegalStateException("Strange type: " + g.getType());
			}
		} else {
			x.setPathParent(p.getPathParent());
			p.setPathParent(null);
		}
	}
	
	private final static <V> void ZigZig(AuxVertex<V> x) {
		if (x.isRoot()) throw new AssertionError();
		if (x.getParent().isRoot()) throw new AssertionError();
		Zig(x.getParent());
		Zig(x);
	}
	
	private final static <V> void ZigZag(AuxVertex<V> x) {
		if (x.isRoot()) throw new AssertionError();
		if (x.getParent().isRoot()) throw new AssertionError();
		Zig(x);
		Zig(x);
	}
}
